{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Prefix Divisible By 5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: prefixesDivBy5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #可被 5 整除的二进制前缀"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二进制数组 <code>nums</code> (&nbsp;<strong>索引从0开始&nbsp;</strong>)。</p>\n",
    "\n",
    "<p>我们将<code>x<sub>i</sub></code>&nbsp;定义为其二进制表示形式为子数组&nbsp;<code>nums[0..i]</code>&nbsp;(从最高有效位到最低有效位)。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，如果 <code>nums =[1,0,1]</code> ，那么&nbsp;<code>x<sub>0</sub>&nbsp;= 1</code>,&nbsp;<code>x<sub>1</sub>&nbsp;= 2</code>, 和&nbsp;<code>x<sub>2</sub>&nbsp;= 5</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回布尔值列表&nbsp;<code>answer</code>，只有当&nbsp;<code>x<sub>i</sub></code><em>&nbsp;</em>可以被 <code>5</code>&nbsp;整除时，答案&nbsp;<code>answer[i]</code> 为&nbsp;<code>true</code>，否则为 <code>false</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0,1,1]\n",
    "<strong>输出：</strong>[true,false,false]\n",
    "<strong>解释：</strong>\n",
    "输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为 true 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,1]\n",
    "<strong>输出：</strong>[false,false,false]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code><sup>&nbsp;</sup></li>\n",
    "\t<li><code>nums[i]</code>&nbsp;仅为&nbsp;<code>0</code>&nbsp;或&nbsp;<code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-prefix-divisible-by-5](https://leetcode.cn/problems/binary-prefix-divisible-by-5/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-prefix-divisible-by-5](https://leetcode.cn/problems/binary-prefix-divisible-by-5/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,1]', '[1,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:\n",
    "        result = []\n",
    "        num = 0\n",
    "        for bit in nums:\n",
    "            num = (num * 2 + bit) % 5\n",
    "            result.append(num == 0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:\n",
    "        ans = []\n",
    "        bin_num = ''\n",
    "        for i in range(len(nums)):\n",
    "            bin_num += str(nums[i]) \n",
    "            if int(bin_num,2)%5==0:\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:\n",
    "        snums = \"\".join(map(lambda x: str(x), nums))\n",
    "\n",
    "\n",
    "        res = []\n",
    "        for i in range(len(snums), 0, -1):\n",
    "            if int(snums[:i], 2) % 5 == 0:\n",
    "                res.append(True)\n",
    "            else:\n",
    "                res.append(False)\n",
    "        res.reverse()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:\n",
    "\n",
    "        res = []\n",
    "\n",
    "        tmp = []\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "\n",
    "            tmp.append(str(nums[i]))\n",
    "\n",
    "            if int(''.join(tmp), 2) % 5 == 0:\n",
    "\n",
    "                res.append(True)\n",
    "\n",
    "            else:\n",
    "\n",
    "                res.append(False)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prefixesDivBy5(self, A: List[int]) -> List[bool]:\n",
    "        tsum=0\n",
    "        for i,num in enumerate(A):\n",
    "            tsum=(tsum*2+num)%5\n",
    "            A[i]=(tsum==0)\n",
    "        return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prefixesDivBy5(self, A: List[int]) -> List[bool]:\n",
    "        import numpy as np\n",
    "        x=0\n",
    "        s=[]\n",
    "        for i in range(len(A)):\n",
    "            x = x*2+A[i]\n",
    "            if x%5==0:\n",
    "                s.append(True)\n",
    "            else:\n",
    "                s.append(False)\n",
    "\n",
    "        return s\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def prefixesDivBy5(self, A: List[int]) -> List[bool]:\n",
    "        N_i=0\n",
    "        answer=[]\n",
    "        # answer=np.zeros((1,len(A)))\n",
    "        # Answer=bool(answer)\n",
    "        for i in range(len(A)):\n",
    "            N_i=N_i*2+A[i]\n",
    "            # answer.add(N_i%5==0)\n",
    "            if N_i%5==0:\n",
    "                # Answer[i]=bool(1)\n",
    "                answer.append(True)\n",
    "            else:\n",
    "                # Answer[i]=bool(0)\n",
    "                answer.append(False)\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prefixesDivBy5(self, A: List[int]) -> List[bool]:\n",
    "        for i in range(1, len(A)):\n",
    "            A[i] = A[i-1] * 2 + A[i]\n",
    "        for i in range(len(A)):\n",
    "            A[i] = A[i] % 5 == 0\n",
    "        return A \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prefixesDivBy5(self, A: List[int]) -> List[bool]:\n",
    "        ans=[A[0]]\n",
    "        for i in range(1, len(A)):\n",
    "            ans.append(ans[-1]*2+A[i])\n",
    "        return [True if a%5==0 else False for a in ans]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prefixesDivBy5(self, A: List[int]) -> List[bool]:\n",
    "        res = []\n",
    "        for i in range(len(A)):\n",
    "            if i:\n",
    "                A[i] = A[i] + (A[i-1] << 1)\n",
    "\n",
    "            if A[i] % 5 == 0:\n",
    "                res.append(True)\n",
    "            else:\n",
    "                res.append(False)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:\n",
    "        ans = []\n",
    "        tmp = 0\n",
    "        for i in range(len(nums)):\n",
    "            ans.append(nums[i]+tmp*2)\n",
    "            tmp = ans[i]\n",
    "        re = []\n",
    "        for i in range(len(ans)):\n",
    "            if ans[i]%5==0:\n",
    "                re.append(True)\n",
    "            else:\n",
    "                re.append(False)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:\r\n",
    "        l = len(nums)\r\n",
    "        banlist = [nums[0]]\r\n",
    "        boollist = [not bool(nums[0] % 5)]\r\n",
    "        for i in range(1, l):\r\n",
    "            k = (banlist[i-1] << 1) + nums[i]\r\n",
    "            banlist.append(k)\r\n",
    "            boollist.append(not bool(k % 5))\r\n",
    "        return boollist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:\n",
    "        l=[]\n",
    "        n=0\n",
    "        res=[]\n",
    "        for i in nums:\n",
    "            n=n*2+i\n",
    "            l.append(n)\n",
    "        for j in l:\n",
    "            res.append(j%5==0)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
